package 剑指offer;

import java.util.ArrayList;
import java.util.Collections;

/**
 * Created by yang on 2016/8/24.
 */
public class ReverseListNode {
    // 非递归
    public ListNode ReverseList(ListNode head) {

        ListNode nodeOfre = null;
        ListNode nodeOfnext = null;

        while (head != null) {
            // 保存head的后续节点
            nodeOfnext = head.next;
            // 保存nodeOfpre的后续节点
            head.next = nodeOfre;
            // 插入head节点到nodeOfpre
            nodeOfre = head;
            // 恢复head的后续节点
            head = nodeOfnext;
        }

        return nodeOfre;

    }

    // 递归
    public ListNode ReverseList01(ListNode head) {

        // 递归结束条件
        if (head == null || head.next == null) {
            return head;
        }
        // 1 2 3 4 5
        ListNode nodeOftmp = head.next;
        head.next = null;
        ListNode nodeOfre = ReverseList01(nodeOftmp);
        nodeOftmp.next = head;
        return nodeOfre;
    }

    // 新建链表
    public ListNode ReverseList02(ListNode head) {

        ArrayList<ListNode> arrayList = new ArrayList<ListNode>();

        if(head == null)
            return null;

        while(head != null) {
            arrayList.add(head);
            head = head.next;
        }

        Collections.reverse(arrayList);

        ListNode nodeOfre = arrayList.get(0);
        ListNode nodeOftmp = nodeOfre;

        for(ListNode n:arrayList) {
            nodeOftmp.next = n;
            nodeOftmp = nodeOftmp.next;
        }

        return nodeOfre;
    }
}
